#include <iostream>
#include <vector>
#include <list>
using namespace std;
template <typename DT>
struct edge{
    int v;
    int w;
    DT pathweight;
};
template <typename DT>
class graph{
private:
    int maxnumber;
    vector<int> vertex;
    vector<vector<DT>> adj_matrix;
    vector<list<edge<DT>>> adj_list; 
    bool adj_type=true;
    bool isdirection=true;
public:
    // graph(vector<int> &_vertex,vector<list<edge<DT>>> &_adj_list,int &_maxnumber,bool _isdirection=true){
    //     vertex=_vertex;
    //     adj_list=_adj_list;
    //     maxnumber=_maxnumber;
    //     isdirection=_isdirection;
    // }
    // graph(vector<int> &_vertex,vector<vector<DT>> &_adj_matrix,int &_maxnumber,bool _isdirection=true){
    //     vertex=_vertex;
    //     adj_matrix=_adj_matrix;
    //     adj_type=false;
    //     maxnumber=_maxnumber;
    //     isdirection=_isdirection;
    // }
    graph(vector<int> _vertex,int &_maxnumber,bool _isdirection=true,bool _adj_type=true){

        vertex=_vertex;
        maxnumber=_maxnumber;
        isdirection=_isdirection;
        adj_type=_adj_type;
        if(adj_type==true){
            for(int i=0;i<=vertex.size();i++)
            {
                adj_list.push_back(list<edge<DT>>());
            }   
        }else{
            vector<DT> v;
            for(int i=0;i<=maxnumber;i++){
                v.push_back(0);
            }
            for(int i=0;i<=maxnumber;i++){
                adj_matrix.push_back(v);
            }
        }

    }
    void addedge(edge<DT> _edge){
        if(adj_type==true){
            if(isdirection==true){
                adj_list[_edge.v].push_back(_edge);
            }else{
                adj_list[_edge.v].push_back(_edge);
                std::swap(_edge.v,_edge.w);
                adj_list[_edge.v].push_back(_edge);
            }

        }else{
            if(isdirection==true){
                adj_matrix[_edge.v][_edge.w]=_edge.pathweight;    
            }else{
                adj_matrix[_edge.v][_edge.w]=_edge.pathweight;
                adj_matrix[_edge.w][_edge.v]=_edge.pathweight;
            } 
        }
    }
    void listVertexes(){
        for(auto e:vertex){
            cout<< e<< " ";
        }
        cout<<endl;
    }
    void listEdges(){
        if(adj_type==true){
            for(int i=0;i<=vertex.size();i++){
                for(auto e=adj_list[i].begin();e !=adj_list[i].end();e++){
                    cout<< "("<< e->v<<","<<e->w<<","<<e->pathweight<<")"<<endl;
                }
            }
        }else{
            for(int i=1;i<=maxnumber;i++){
                for(int j=1;j<=maxnumber;j++){
                    if(adj_matrix[i][j]!=0){
                        cout<< "("<< i<<","<<j<<","<<adj_matrix[i][j]<<")"<<endl;
                    }
                }
            }
        }
    }
};
